Search for: All records

The 𝑊 -random graphs provide a flexible framework for modeling large random networks. Using the Large Deviation Principle (LDP) for 𝑊 -random graphs from [19], we prove the LDP for the corresponding class of random symmetric Hilbert-Schmidt integral operators. Our main result describes how the eigenvalues and the eigenspaces of the integral operator are affected by large deviations in the underlying random graphon. To prove the LDP, we demonstrate continuous dependence of the spectral measures associated with integral operators on the corresponding graphons and use the Contraction Principle. To illustrate our results, we obtain leading order asymptotics of the eigenvalues of small-world and bipartite random graphs conditioned on atypical edge counts. These examples suggest several representative scenarios of how the eigenvalues and the eigenspaces are affected by large deviations. We discuss the implications of these observations for bifurcation analysis of Dynamical Systems and Graph Signal Processing. 

Abstract The Fourier and Fourier–Stieltjes algebras over locally compact groupoids have been defined in a way that parallels their construction for groups. In this article, we extend the results on surjectivity or lack of surjectivity of the restriction map on the Fourier and Fourier–Stieltjes algebras of groups to the groupoid setting. In particular, we consider the maps that restrict the domain of these functions in the Fourier or Fourier–Stieltjes algebra of a groupoid to an isotropy subgroup. These maps are continuous contractive algebra homomorphisms. When the groupoid is étale, we show that the restriction map on the Fourier algebra is surjective. The restriction map on the Fourier–Stieltjes algebra is not surjective in general. We prove that for a transitive groupoid with a continuous section or a group bundle with discrete unit space, the restriction map on the Fourier–Stieltjes algebra is surjective. We further discuss the example of an HLS groupoid, and obtain a necessary condition for surjectivity of the restriction map in terms of property FD for groups, introduced by Lubotzky and Shalom. As a result, we present examples where the restriction map for the Fourier–Stieltjes algebra is not surjective. Finally, we use the surjectivity results to provide conditions for the lack of certain Banach algebraic properties, including the (weak) amenability and existence of a bounded approximate identity, in the Fourier algebra of étale groupoids. 

The spectral decomposition of graph adjacency matrices is an essential ingredient in the design of graph signal processing (GSP) techniques. When the adjacency matrix has multi-dimensional eigenspaces, it is desirable to base GSP constructions on a particular eigenbasis that better reflects the graph’s symmetries. In this paper, we provide an explicit and detailed representation-theoretic account for the spectral decomposition of the adjacency matrix of a weighted Cayley graph. Our method applies to all weighted Cayley graphs, regardless of whether they are quasi-Abelian, and offers detailed descrip- tions of eigenvalues and eigenvectors derived from the coefficient functions of the representations of the underlying group. Next, we turn our attention to constructing frames on Cayley graphs. Frames are overcomplete spanning sets that ensure stable and potentially redundant systems for signal re- construction. We use our proposed eigenbases to build frames that are suitable for developing signal processing on Cayley graphs. These are the Frobenius–Schur frames and Cayley frames, for which we provide a characterization and a practical recipe for their construction. 

This paper investigates the Robinson graphon completion/recovery problem within the class of $L^p$-graphons, focusing on the range $$5 5$, any $L^p$-graphon $$w$$ can be approximated by a Robinson graphon, with error of the approximation bounded in terms of $$\Lambda(w)$$. When viewing $$w$$ as a noisy version of a Robinson graphon, our method provides a concrete recipe for recovering a cut-norm approximation of a noiseless $$w$$. Given that any symmetric matrix is a special type of graphon, our results can be applicable to symmetric matrices of any size. Our work extends and improves previous results, where a similar question for the special case of $$L^\infty$$-graphons was answered.